package com.jp.algorithm.linkList;


public class DoubleLinkedList {

    Node first;
    Node last;

    public DoubleLinkedList() {
    }

    class Node {
        public int item;
        public Node pre=null;
        public Node next=null;

        public Node(int e){
            this.item=e;
        }
    }

    public void addLast(int item) {
        Node node = new Node(item);
        Node l = last;
        node.pre = l;
        last = node;
        if (l == null) {
            first = node;
        } else {
            l.next = node;
        }
    }

    public void addFirst(int item) {
        Node node = new Node(item);
        Node f = first;
        node.next = f;
        first = node;
        if (f == null) {
            last = node;
        } else {
            f.pre = node;
        }
    }


    public Node delete(Node node) {
        if (first == null)
            return null;
        Node pre = node.pre;
        Node next = node.next;
        if (pre == null) {
            first = next;
        } else {
            pre.next = node.next;
            node.pre = null;
        }
        if (next == null) {
            last = pre;
        } else {
            next.pre = pre;
            node.next = null;
        }
        return null;
    }

    public void insert(int index, Node node) {

    }

    public void quichSort(Node start, Node end) {
        if(start == end || start == null || end == null){
            return;
        }
        Node low = start;
        Node high = end;
        int tmp = low.item;
        while(low != high){

            while(low != high){
                if(high.item >= tmp){
                    high = high.pre;
                }else{
                    low.item=high.item;
                    break;
                }
            }

            while(low != high){
                if(low.item <= tmp){
                    low = low.next;
                }else{
                    high.item=low.item;
                    break;
                }
            }
        }
        low.item = tmp;
        quichSort(start,low.pre);
        quichSort(low.next,end);
    }


    public Node getNode(int index) {
        Node cur = first;
        while (cur != null) {
            index--;
            cur = cur.next;
            if (index == 0)
                return cur;
        }
        return null;
    }

    public void print() {
        Node cur = first;
        while (cur != null) {
            System.out.println("item:" + cur.item);
            cur = cur.next;
        }
    }


    public static void main(String[] args) {
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();

        doubleLinkedList.addLast(10);
        doubleLinkedList.addLast(5);
        doubleLinkedList.addLast(30);
        doubleLinkedList.addLast(1);
        doubleLinkedList.addLast(4);
        doubleLinkedList.addLast(12);
        doubleLinkedList.print();

        doubleLinkedList.quichSort(doubleLinkedList.first,doubleLinkedList.last);


        doubleLinkedList.print();




    }
}
